ST_ClusterIntersectingWin and ST_ClusterWithinWin #721

pramsey · 2023-02-24T18:38:29Z

Access the functionality of ST_ClusterIntersecting and ST_ClusterWithin, but using a window function instead of getting back a big lump of GeometryCollection.

robe2 · 2023-02-25T02:39:19Z

Your NEWs note should reference GH721

robe2 · 2023-02-25T02:49:36Z

doc/reference_cluster.xml

+        <funcsynopsis>
+          <funcprototype>
+            <funcdef>integer <function>ST_ClusterIntersectingWin</function></funcdef>
+            <paramdef><type>geometry</type> <parameter>g</parameter></paramdef>


Suggested change

<paramdef><type>geometry</type> <parameter>g</parameter></paramdef>

<paramdef><type>geometry winset </type> <parameter>geom</parameter></paramdef>

I'd change to geom to be consistent with the other functions, unless you plan to at some point in time make this work for geography, might be a good time to experiment with anyelement :)

The winset is fluff to flag it as a window function so the garden test can test it and it also appears in the 15.2. PostGIS Window Functions section.

robe2 · 2023-02-25T02:50:38Z

doc/reference_cluster.xml

+        <funcsynopsis>
+          <funcprototype>
+            <funcdef>integer <function>ST_ClusterWithinWin</function></funcdef>
+            <paramdef><type>geometry </type> <parameter>g</parameter></paramdef>


Suggested change

<paramdef><type>geometry </type> <parameter>g</parameter></paramdef>

<paramdef><type>geometry winset </type> <parameter>geom</parameter></paramdef>

Same as mentioned in other

robe2 · 2023-02-25T02:52:31Z

NEWS

@@ -15,6 +15,7 @@ xxxx/xx/xx
  - #5286, RenameTopoGeometryColumn (Sandro Santilli)
  - GH703, Add min/max resampling as options (Christian Schroeder)
  - #5336, topogeometry cast to topoelement support (Regina Obe)
+  - New window-based ST_ClusterWithinWin and ST_ClusterIntersectingWin (Paul Ramsey)


Suggested change

- New window-based ST_ClusterWithinWin and ST_ClusterIntersectingWin (Paul Ramsey)

- GH721, New window-based ST_ClusterWithinWin and ST_ClusterIntersectingWin (Paul Ramsey)

robe2

Added more changes - the availability should be 3.4.0 not 3.4

robe2 · 2023-02-25T03:00:37Z

postgis/postgis.sql.in

+	LANGUAGE 'c' IMMUTABLE STRICT WINDOW PARALLEL SAFE
+	_COST_HIGH;
+
+-- Availability: 3.4


Suggested change

-- Availability: 3.4

-- Availability: 3.4.0

dbaston · 2023-02-27T00:50:22Z

doc/reference_cluster.xml

+      <refsection>
+        <title>Description</title>
+
+        <para>ST_ClusterWithinWin is a window function that returns an integer for each input geometry, where the integer the cluster number the geometry is a member of. Clusters represent a set of input geometries separated by no more than the specified distance. (Distances are Cartesian distances in the units of the SRID.)


Worth mentioning that this function is equivalent to ST_ClusterDBSCAN(eps, minPoints:=0) ?

Are they fully equivalent? In behaviour as well as performance? If so, perhaps only one is needed?

Yes, ST_ClusterWithin just calls DBSCAN.

If it's equivalent to ST_ClusterDBSCan, then yah we should not bother adding it. One less function and then just add an addendum to the docs.

@dbaston

Worth mentioning that this function is equivalent to ST_ClusterDBSCAN(eps, minPoints:=0) ?

Is there a reason you didn't set minPoints as default arg with value 0?

OTOH, seems to me that there could be a faster implementation for ClusterWithin (since unlike DBSCAN it is a deterministic function which doesn't have to be interative). So providing an specific API for it will allow a future optimized implementation, and lets users be specific about what they want to compute.

DBSCAN with minPoints=0 is deterministic. I'm not sure what you would propose changing about it? I have no opinion on adding a new function or not, I just thought it would be good to point out the equivalency in the docs.

(It's already special-cased, if that's what you're getting at)

postgis/liblwgeom/lwgeom_geos_cluster.c

Lines 514 to 520 in 1a004f4

int union_dbscan(LWGEOM** geoms, uint32_t num_geoms, UNIONFIND* uf, double eps, uint32_t min_points, char** in_a_cluster_ret)

{

if (min_points <= 1)

return union_dbscan_minpoints_1(geoms, num_geoms, uf, eps, in_a_cluster_ret);

else

return union_dbscan_general(geoms, num_geoms, uf, eps, min_points, in_a_cluster_ret);

}

It's already special-cased

Well, that's a good optimization. And seems like it might actually be the optimal implementation for Cluster-Within? (A bit hard to tell, since the generality makes the algorithm somewhat obscure).

Anyway, the documentation for ST_ClusterDBSCAN has a complex description which does not make it easy to deduce that it is also useful for a deterministic Cluster-Within functionality. So having a separate function and doc page seems ideal.

Yes, my suggestion was only to document the equivalence.

dbaston · 2023-02-27T00:53:29Z

doc/reference_cluster.xml

+        </para>
+
+        <para>Availability: 3.4.0</para>
+      </refsection>


Suggested change

</refsection>

<para>&curve_support;</para>

</refsection>

By the same token should ClusterIntersecting have this marker? I'm not sure if it means "native arc support" (like distance and area have) or "stroked arc support" (like all the GEOS backed functions have).

I guess I would interpret it to mean native arc support, otherwise all functions would have arc support, no? (But I agree, the wording isn't clear one way or the other.) In this case ClusterWithin would have native arc support but ClusterIntersecting uses GEOS so it would not.

DBScan is not currently marked as having arc support. add there too?

dbaston · 2023-02-27T01:01:00Z

doc/reference_cluster.xml

+        <title>Description</title>
+
+        <para>ST_ClusterIntersectingWin is a windowing function that builds inter-connecting clusters of geometries that intersect. It is possible to traverse all geometries in a cluster without leaving the cluster. The return value is the cluster number that the geometry argument participates in, or null for null inputs.</para>
+


This could also be expected to be equivalent to ST_ClusterDBSCAN(0, 0), if not for cases where ST_Distance(a,b) == 0 but ST_Intersects(a, b) is false.

robe2 · 2023-02-27T04:32:50Z

@pramsey I investigated the error cirrus errors. It's happening when Cirrus CI is testing dumprestore.

I run into the same issue if I do:

make check RUNTESTFLAGS="-v --dumprestore"

But works fine

make check RUNTESTFLAGS="--extension -v --dumprestore"

I'm going to flip Cirrus CI to test against extension based install, since that's really what we care about these days anyway.

I'll ticket this as a separate issue in postgis_restore.pl

Was doing script installed dumprestore check which causes a failure in #721 Dumprestore Issue references #5348

strk · 2023-02-27T21:39:13Z

Could you please rebase against current master branch, resolving conflicts, to see if it fixes the --dumprestore test ?

robe2 · 2023-03-04T01:17:05Z

@pramsey Can we close this out since you've already committed it or is there a reason it is still open?

robe2 requested changes Feb 25, 2023

View reviewed changes

dbaston reviewed Feb 27, 2023

View reviewed changes

strk pushed a commit that referenced this pull request Feb 27, 2023

Change Cirrus to do extension based dumprestore

9ea9b67

Was doing script installed dumprestore check which causes a failure in #721 Dumprestore Issue references #5348

pramsey added 10 commits February 27, 2023 13:39

ST_ClusterWithinWin

d57e281

ST_ClusterIntersectingWin

4a517ff

trailing spaces

f392f8d

doco

3c6d73b

doco

f0dc2db

rebase

44608e6

change param name

6e1a239

ignore config file

a9f6369

rebase

243123c

note arc support

b741b22

pramsey force-pushed the master-window-cluster branch from 96e718d to b741b22 Compare February 27, 2023 21:41

postgis deleted a comment from robe2 Feb 27, 2023

Add note to WithinWin on DBSCAN

fc01c1b

pramsey closed this Mar 4, 2023

pramsey deleted the master-window-cluster branch May 25, 2023 15:34

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ST_ClusterIntersectingWin and ST_ClusterWithinWin #721

ST_ClusterIntersectingWin and ST_ClusterWithinWin #721

pramsey commented Feb 24, 2023

robe2 commented Feb 25, 2023

robe2 Feb 25, 2023

robe2 Feb 25, 2023

robe2 Feb 25, 2023

robe2 left a comment

robe2 Feb 25, 2023

dbaston Feb 27, 2023

dr-jts Feb 27, 2023

dbaston Feb 27, 2023

robe2 Feb 27, 2023

robe2 Feb 27, 2023

dr-jts Feb 27, 2023

dbaston Feb 27, 2023

dbaston Feb 27, 2023

dr-jts Feb 27, 2023

dbaston Feb 27, 2023

dbaston Feb 27, 2023

pramsey Feb 27, 2023

dbaston Feb 27, 2023

pramsey Feb 27, 2023

dbaston Feb 27, 2023

dbaston Feb 27, 2023

robe2 commented Feb 27, 2023

strk commented Feb 27, 2023

robe2 commented Mar 4, 2023

	<paramdef><type>geometry</type> <parameter>g</parameter></paramdef>
	<paramdef><type>geometry winset </type> <parameter>geom</parameter></paramdef>

	<paramdef><type>geometry </type> <parameter>g</parameter></paramdef>
	<paramdef><type>geometry winset </type> <parameter>geom</parameter></paramdef>

	- New window-based ST_ClusterWithinWin and ST_ClusterIntersectingWin (Paul Ramsey)
	- GH721, New window-based ST_ClusterWithinWin and ST_ClusterIntersectingWin (Paul Ramsey)

	int union_dbscan(LWGEOM** geoms, uint32_t num_geoms, UNIONFIND* uf, double eps, uint32_t min_points, char** in_a_cluster_ret)
	{
	if (min_points <= 1)
	return union_dbscan_minpoints_1(geoms, num_geoms, uf, eps, in_a_cluster_ret);
	else
	return union_dbscan_general(geoms, num_geoms, uf, eps, min_points, in_a_cluster_ret);
	}

		<title>Description</title>

		<para>ST_ClusterIntersectingWin is a windowing function that builds inter-connecting clusters of geometries that intersect. It is possible to traverse all geometries in a cluster without leaving the cluster. The return value is the cluster number that the geometry argument participates in, or null for null inputs.</para>

ST_ClusterIntersectingWin and ST_ClusterWithinWin #721

ST_ClusterIntersectingWin and ST_ClusterWithinWin #721

Conversation

pramsey commented Feb 24, 2023

robe2 commented Feb 25, 2023

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

robe2 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

robe2 commented Feb 27, 2023

strk commented Feb 27, 2023

robe2 commented Mar 4, 2023